package eda.hashTable;

import java.lang.reflect.Array;

import eda.util.ADTNoSuchElement;
import eda.util.ADTOverflowException;
import eda.util.ADTUnderflowException;
import eda.util.Constants;

/**
 * Estrutura representa uma tabela hash que funciona tanto com enderecamento
 * fechado (com chaining) quanto como enderecamento aberto. No caso de
 * enderecamento aberto ela pode funcionar com linear probe, probe quadratico ou
 * double hashing. A forma de como a tabela vai trabalhar depende das
 * informacoes fornecidas pelo usuario (se enderecamento aberto ou fechado, e se
 * enderecamento aberto que tipo de probe). A estrutura deve ter um tamanho
 * inicial, um tamanho maximo que pode crescer e um FATOR de crescimento. Quando
 * instanciada a estrutura tem um tamanho inicial. Quando ela vai crescendo e
 * atinge 75% de sua capacidade, ela aumenta de tamanho (e deve fazer um rehash
 * nos elementos) de acordo com o fator de crescimento desde que nao atinja ou
 * ultrapasse o tamanho maximo. A partir dai a estrutura nao pode mais crescer e
 * pode ficar cheia. Use as constantes definidas em eda.util.Constantes para
 * inicializar os valores internos de sua estrutura. Faca protected qualquer
 * outro metodo auxiliar.
 */
public class HashTableProbe<K, V> implements HashTable<K, V> {

	private HashProbeElement<K, V>[] table;
	private int numberOfElements;
	private final double MULTIPLICATION_CONSTANT = (double)(Math.sqrt(5) - 1)/2;

	private int probe;
	private int idealPrime;

	private final int LINEAR_PROBE = -1;
	private final int QUADRATIC_PROBE = 0;
	private final int DOUBLE_PROBE = 1;

	@SuppressWarnings("unchecked")
	public HashTableProbe(int probe) {
		this.probe = probe;
		this.numberOfElements = 0;
		this.table = (HashProbeElement<K, V>[]) Array.newInstance(
				HashProbeElement.class, Constants.INITIAL_SIZE_OF_STRUCTURE);
		this.idealPrime = calculateIdealPrime(Constants.INITIAL_SIZE_OF_STRUCTURE);

	}

	protected int hashLinearProbe(K key, int i) {
		int a = key.hashCode();
		int place = (int) (a % idealPrime);
		int place2 = (place + i) % this.table.length;

		return place2;
	}

	protected int hashQuadraticProbe(K key, int i) {
		int a = key.hashCode();
		int h = (int) (table.length * ((a * MULTIPLICATION_CONSTANT) % 1));
		int place = (int)(h + 3 * (i * i) + i) % table.length;

		return place;
	}

	protected int hashDouble(K key, int i) {
		int a = key.hashCode();
		
		int biggestPrime = calculateBiggestPrimeThatIsSmallerThan(table.length);
		int lowestPrime = calculateBiggestPrimeThatIsSmallerThan(biggestPrime);
		
		int h1 = (int) (table.length * (a * MULTIPLICATION_CONSTANT));
		int h2 = Math.abs((int) ( (a + 1) % ( lowestPrime == 2 ? 1 : lowestPrime )));
		int place = (h1 + (i * h2)) % biggestPrime;

		return place;
	}

	private int calculateIdealPrime(int i) {
		while (!isPrime(i-1))
			i++;
		return i;
	}
	
	private int calculateBiggestPrimeThatIsSmallerThan(int i ){
		while (!isPrime(i))
			i--;
		return i;		
	}
	

	private boolean isPrime(int i) {
		if (i % 2 == 0) {
			return false;
		} else {
			for (int j = Constants.INITIAL_SIZE_OF_STRUCTURE; j < i / 2; j++) {
				if (i % j == 0)
					return false;
			}
		}
		return true;
	}

	@Override
	public boolean isEmpty() {
		return this.numberOfElements == 0;
	}

	@Override
	public boolean full() {
		return this.numberOfElements == Constants.MAX_SIZE_OF_STRUCTURE;
	}

	@Override
	public int size() {
		return this.numberOfElements;
	}

	@Override
	public void insert(K key, V value) throws ADTOverflowException {

		int i = 0;
		
		if (full()) {
			throw new ADTOverflowException();
		}

		int index = hashPosition(key, i);
	
		while(table[index] != null && !(this.table[index].isDeleted()) && i < this.size() && !(table[index].getKey().equals(key))){
			
			i++;
			index = hashPosition(key, i);
			
		}

		if ( table[index] == null || table[index].isDeleted() ){
			this.numberOfElements++;
			table[index] = new HashProbeElement<K, V>(key, value);
		}
		else if (!table[index].getKey().equals(key)){
			int myRealProbe = this.probe; //Essa eh a solucao que encontramos para sanar os casos onde insercoes falham
			this.probe = -1;			  //para quadratic e double hashing (qdo a tabela tah com mais da metade ocupada e seu tamanho
			insert(key, value);			  //eh um numero primo isso pode acontecer: a fc de hash sempre dah colisoes)
			this.probe = myRealProbe;
		}
		else{
			table[index] = new HashProbeElement<K, V>(key, value); //Qdo a chave eh igual, acontece um override			
		}
				
		if (this.numberOfElements >= (int) table.length * 0.75
				&& table.length < Constants.MAX_SIZE_OF_STRUCTURE) {
			rehash(this.table);
		}

	}

	@Override
	public void remove(K key) throws ADTUnderflowException, ADTNoSuchElement {
		if(numberOfElements==0){
			throw new ADTUnderflowException();
		}
		HashProbeElement<K, V> result = internalQuery(key);
		if(result == null){
			throw new ADTNoSuchElement();			
		}
		else {
			result.setDeleted(true);
			this.numberOfElements--;
		}
	}

	@Override
	public V search(K key) {
		HashProbeElement<K, V> result = internalQuery(key);
	
		if(result!=null){
			return result.getValue();			
		}
		return null;
	}
	
	protected HashProbeElement<K, V> internalQuery(K key) {
		int i = 0;
		int index = 0;

		index = hashPosition(key, i);
		
		while (this.table[index] != null && i<=this.size() ) {

			if (this.table[index].getKey().equals(key) && !(this.table[index].isDeleted())) {
				return this.table[index];
			}
			i++;
			index = hashPosition(key, i);
			
		}
		
		return null;
	}

	@Override
	public boolean containsKey(K key) {
		return search(key) != null;
	}

	private int hashPosition(K key, int counter) {
		int hashPosition = 0;

		switch (probe) {
		case LINEAR_PROBE: {
			hashPosition = hashLinearProbe(key, counter);
			break;
		}
		case QUADRATIC_PROBE: {
			hashPosition = hashQuadraticProbe(key, counter);
			break;
		}
		case DOUBLE_PROBE: {
			hashPosition = hashDouble(key, counter);
			break;
		}
		}

		if (hashPosition < 0) {
			hashPosition += table.length;
		}
		
		return hashPosition;
	}

	@SuppressWarnings("unchecked")
	protected void rehash(HashProbeElement<K, V>[] oldTable) {
		if (!(oldTable.length + Constants.INCREASING_FACTOR >= Constants.MAX_SIZE_OF_STRUCTURE)) {
			table = (HashProbeElement<K, V>[]) Array.newInstance(
					HashProbeElement.class, oldTable.length
							+ Constants.INCREASING_FACTOR);
		} else {
			table = (HashProbeElement<K, V>[]) Array.newInstance(
					HashProbeElement.class, Constants.MAX_SIZE_OF_STRUCTURE);
		}
		this.numberOfElements = 0;
		this.idealPrime = calculateIdealPrime(oldTable.length
				+ Constants.INCREASING_FACTOR);
		try {
			for (HashProbeElement<K, V> element : oldTable) {
				if (element != null && !element.isDeleted()) {
					insert(element.getKey(), element.getValue());
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public String toString(){
		String toReturn = "[ ";
		
		for (int i = 0; i < this.table.length; i++) {
			if (i != this.table.length - 1) {
				if(table[i] != null){
					if(table[i].isDeleted()){
						toReturn += i + " = " + "[DELETED]" + ", ";
					}else{
						toReturn += i + " = " + "[" + table[i].toString()+ "]" + ", ";
					}
						
				}else{
					toReturn += i + " = " + "[]" + ", ";
				}
			}
			else {
				if(table[i] != null){
					if(table[i].isDeleted()){
						toReturn += i + " = " + "[DELETED]";
					}else{
						toReturn += i + " = " + "[" +table[i].toString() +"]";
					}
						
				}else{
					toReturn += i + " = " + "[]";
				}
			}
		}
		toReturn += " ]";
		
		return toReturn;
	}
	
}